#include <bits/stdc++.h>
#define ru(i,l,r) for(int i=(l);i<=(r);i++)
#define ru_(i,l,r) for(int i=(l);i<(r);i++)
#define rd(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int,int>

using namespace std;

// 枚举模拟， 排列枚举， ,并查集
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> s;
        ru_(i,0,nums.size()){
            if(nums[i]<k) return -1;
            if(nums[i]!=k) s.insert(nums[i]);
        }; return s.size();
    }
};
class Solution2{
public:
    int findMinimumTime(vector<int>& strength, int k) {
        int n=strength.size(); vector<int> v(n);
        ru_(i,0,n) v[i]=i;
        int ans=INT_MAX;
        do{
            ll t=0,a=1,b=0;
            ru_(i,0,n){
                int idx=v[i], s=strength[idx];
                if(b<s){ll d=(ll)(s-b+a-1)/a; t+=d; b+=a*d;}
                b=0; a+=k;
            }
            if(t<ans) ans=(int)t;
        } while(next_permutation(v.begin(),v.end()));
        return ans;
    }
};
class Solution3 {
public:
    const int M=INT_MAX;
    vector<bool> deal(int a){
        vector<bool> v(a+1,true);
        v[0]=v[1]=false;
        for(int i=2;i*i<=a;i++){
            if(v[i])
                for(int j=i*i;j<=a;j+=i) v[j]=false;
        }; return v;
    }
    vector<int> solve(int num, const vector<bool>& v, int k){
        vector<int> ne;
        string s = to_string(num);
        while(s.size() < k) s = "0" + s;
        for(int i = 0; i < k; ++i){
            if(s[i] < '9'){
                string a = s;
                a[i] += 1;
                if(i == 0 && a[i] == '0') continue;
                int c = stoi(a);
                if(to_string(c).length() == k && !v[c]){
                    ne.push_back(c);
                }
            }
            if(s[i] > '0'){
                if(i == 0 && s[i] == '1') continue;
                string d = s;
                d[i] -= 1;
                if(i == 0 && d[i] == '0') continue;
                int c = stoi(d);
                if(to_string(c).length() == k && !v[c]){
                    ne.push_back(c);
                }
            }
        }
        return ne;
    }
    int minOperations(int n, int m) {
        if(to_string(n).length()!= to_string(m).length()) return -1;
        int k= to_string(n).length();
        vector<bool> v= deal(10000);
        if(v[n]||v[m]) return -1;
        if(n==m) return n;
        vector<int> c(10000,M); c[n]=n;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p;
        p.emplace(c[n],n);
        while(!p.empty()){
            auto cur=p.top(); p.pop();
            int ct=cur.first, cnt=cur.second;
            if(cnt==m) return ct;
            if(ct>c[cnt]) continue;
            vector<int> ne=solve(cnt,v,k);
            for(auto &e:ne){
                ll net=(ll)ct+e;
                if(net<c[e]){c[e]=net; p.emplace(c[e],e);}
            }
        }
    }
};

class Node{
public:
    vector<int> fa;
    Node(int n){
        fa.resize(n);
        ru_(i,0,n) fa[i]=i;
    }
    int find(int x){
        if(fa[x]!=x) fa[x]=find(fa[x]);
        return fa[x];
    }
    void work(int x, int y){
        int xx=find(x), yy=find(y);
        if(xx!=yy) fa[yy]=xx;
    }
};
class Solution4 {
public:
    int countComponents(vector<int>& nums, int threshold) {
        vector<int> v; int a;
        for(auto &t:nums){
            if(t<=threshold) v.push_back(t);
            else a++;
        }
        int n=v.size();
        if(n==0) return a;
        vector<int> vis(threshold+1,-1);
        ru_(i,0,n) vis[v[i]]=i;
        Node no(n);
        ru(i,1,threshold){
            vector<int> tmp;
            int c=sqrt(i);
            ru(j,1,c){
                if(i%j==0){
                    if(vis[j]!=-1) tmp.push_back(vis[j]);
                    int k=i/j;
                    if(k!=j&&k<=threshold&&vis[k]!=-1) tmp.push_back(vis[k]);
                }
            }
            if(tmp.size()>=2){
                int fi=tmp[0];
                ru_(i,1,tmp.size()) no.work(fi,tmp[i]);
            }
        }
        unordered_set<int> pa;
        ru_(i,0,n) pa.insert(no.find(i));
        return pa.size()+a;

    }
};
int main(){
    Solution s;
    vector<int> nums1 = {5,2,5,4,5}; int k = 2;
    cout<<s.minOperations(nums1,k)<<endl;

    Solution2 s2;
    vector<int> strength = {3,4,1};
    cout<<s2.findMinimumTime(strength, 1)<<endl;

    Solution3 s3;
    cout<<s3.minOperations(10,12)<<endl;

    Solution4 s4;
    vector<int> nums = {2,4,8,3,9}; int threshold = 5;
    cout<<s4.countComponents(nums, threshold)<<endl;
}
